package cn.cxq.learning.search;

public class HashSearch {

    /**
     * 获取调整之后满足哈希查找条件的数组。
     * @param arr
     * @return
     */
    public static int[] convertIntoHashList(int[] arr){

        int[] hashList = new int[arr.length];

        for (int i = 0; i < hashList.length; i++) {
            hashList[i]=Integer.MIN_VALUE;
        }

        for (int i = 0; i < arr.length; i++) {
            int hashAddress = getHash(arr[i],arr.length);
            while (hashList[hashAddress]!=Integer.MIN_VALUE) {
//                hashAddress = getHash(hashAddress++, arr.length);//这样的写法是不行的，这样的写法传的参数是原本的值，而不是加一后的值，所以会出现错误
//                hashAddress = getHash(++hashAddress, arr.length);//这样写是可以的。
                hashAddress = getHash(hashAddress + 1, arr.length);
            }
            hashList[hashAddress] = arr[i];
        }

        return hashList;
    }

    private static int getHash(int value, int size) {
        return Math.abs(value%size);
    }

    public static int search(int[] arr,int value){

        int hashAddress = getHash(value, arr.length);

        if (arr[hashAddress]==value) return hashAddress;
        hashAddress = getHash(hashAddress + 1, arr.length);

        while (arr[hashAddress]!=Integer.MIN_VALUE&&hashAddress!=getHash(value,arr.length)){
            if (arr[hashAddress]==value) return hashAddress;
            hashAddress = getHash(hashAddress + 1, arr.length);
        }
        return -1;
    }

}
